package ans.p39;

import test.Entrance;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * #      39
 * 名称   组合总和
 * 链接   https://leetcode-cn.com/problems/combination-sum
 * 题解   [1349](https://leetcode-cn.com/problems/combination-sum/solution)
 * 通过率 72.2%
 * 难道   中等
 */

public class Solution {

    @Entrance
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        traceback(ans, candidates, list, target, 0);
        return ans;
    }

    private void traceback(List<List<Integer>> ans, int[] candidates, List<Integer> list, int target, int index) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<>(list));
        }
        for (int i = index; i < candidates.length; i++) {
            list.add(candidates[i]);
            traceback(ans, candidates, list, target - candidates[i], i);
            list.remove(list.size() - 1);
        }


    }
}